use 5.10.0;
use strict;

package Graphics::PlanarVector::PathSegment;

sub _tan { sin($_[0]) / cos($_[0]) }

use constant PI=>atan2(1,1)*4;
use constant ARC_SEG=>2;
use constant ARC_RATIO=>_tan(PI/4/ARC_SEG) * 4/3;

sub _line_sect {
	my ($a0, $t0, $t3, $a3) = @_;
	my $d = $t3^$t0 or return;
	(($a0 - $a3)^$t0) / $d * $t3 + $a3;
}

sub _turns {
	my $seg = shift;
	my $dir = (sort { $b->len2 <=> $a->len2 } $seg->derivative(0, 1))[0];
	my @poly = @{$seg->poly_form->derivative};

	valid_param (0, 1,
		poly(map { $_ ^ $dir } @poly)->roots,
		poly(map { $_ & $dir } @poly)->roots,
	);
}

sub _curv {
	my $poly = shift->poly_form;
	my $d1 = $poly->derivative;
	my $d2 = $d1->derivative;
	map {
		my $d = $d1->poly_eval($_);
		($d & $d) / ($d->normalize^$d2->poly_eval($_))
	} @_
}

sub parallel {
	my ($p, $w, $tol, $tol_r) = @_;
	return $p unless abs($w)>1e-6;

	my @ps = ($p);
	my $ord = $p->order;
	if ($ord > 1) {
		my @e = $p->extrema;
	#	my @e = $p->_turns;
		@ps = map { $_->flat }
			$p->subdivide(map {
				[$_, $p->param_to_point($_) ]
			} @e) if @e >= 2;
	}

	my @ret;
	for my $in (@ps) {
		next unless ref $in;
		if ($in->order == 2) {
			$in = $in->to_cubic;
		}
		my @out;
		given($in->order) {
			when(3) { @out = para3($in, $w, $tol, $tol_r) }
			when(1) { @out = para1($in, $w) }
		}
		unless (@ret) {
			push @ret, @out;
			next
		}
		my ($next, $last) = ($out[0], $ret[-1]);

		unless ($last->{pt}[-1]->veq($next->{pt}[0] )) {
			my $n = -$in->tangent(0);

			if ($in->order > 1) {
				my ($k1, $k2) = ($in->_curv(1),
						$next->_curv(1));
				$n = -$n if (abs($k1) - abs($k2)) > 0;
			}

			push @ret, semicircle_join(
					$last->{pt}[-1], $next->{pt}[0],
					abs($w), $n );
		}
		push @ret, @out;
	}
	@ret;
}

sub para1 {
	my ($seg, $w) = @_;
	my $p = $seg->poly_form;
	my $n = $p->[1]->normalize->rotate(90) * $w;
	from_poly([$p->[0] + $n, $p->[1]])
}

sub para3 {
	my ($seg, $w, $tol, $tol_r) = @_;
	return unless $seg->order == 3;

	my $m = $seg->param_to_point(.5);
	my ($a0, $a1, $a2, $a3) = @{$seg->{pt}};
	my ($b01, $b32) = ($seg->tangent(0), $seg->tangent(1,1));
	my ($b0, $b3) = (
		$seg->{pt}[0]  + $w * ($b01->rotate(90)),
		$seg->{pt}[-1] + $w * ($b32->rotate(90)),
	);
	my $d = ($a3 + $a2 - $a1 - $a0)->normalize;

	my @c1 = ($b01^$d, $b32^$d, ($w + ((($b3 + $b0)/2 - $m)^$d))*-8/3);
	my @c2 = ($c1[0], -$c1[1], 2*(($b3-$b0)^$d));

	my $x = $c1[0]*$c2[1] - $c2[0]*$c1[1];
	my ($a, $b) = (	($c1[2]*$c2[1] - $c2[2]*$c1[1])/$x,
			($c2[2]*$c1[0] - $c1[2]*$c2[0])/$x	);
#	print STDERR @c1;
#	print STDERR @c2;
#	print STDERR "ends", $b0, $b3;
#	print STDERR "vecs", $b01, $b32, $d, $m;
#	print STDERR 'coef', $a, $b;
	my ($b1, $b2) = ($b0 + $b01 * $a, $b3 + $b32 * $b);
	my $err = abs(($m - ($b0 + $b3 + ($b1 + $b2)*3)/8) & $d);

	my $w2 = abs($w);
	$tol //= 1;
	$tol_r //= .2;

	if ($err/$w2 > $tol_r || $err > $tol) {
		return map { $_->para3($w) } $seg->subdivide([0], [.5], [1]);
	}
	path_segment($b0, $b1, $b2, $b3)
}

sub semicircle_join {
	my ($cur, $dest, $r, $n) = @_;

	my $center = ($dest + $cur)/2;
	my $dr = ($cur - $center) * ARC_RATIO;
	my $tip = $center + $n * $r;
	$r *= ARC_RATIO;

	(
		path_segment($cur, $cur + $r * $n, $tip + $dr, $tip),
		path_segment($tip, $tip - $dr, $dest + $n * $r, $dest),
	)
}

sub join_bevel {
	my ($s1, $s2) = @_;
	path_segment($s1->{pt}[-1], $s2->{pt}[0])
}

sub join_miter {
	my ($s1, $s2, $limit) = @_;
	my ($p1, $p2, $n1, $n2) = ($s1->{pt}[-1], $s2->{pt}[0],
		$s1->tangent(1,1), $s2->tangent(0));

	if (($n1 & $n2) < $limit) {
		return join_bevel($s1, $s2);
	}
	my $p = _line_sect($p1, $n1, $n2, $p2) or return;
	(path_segment($p1, $p), path_segment($p, $p2));
}

sub join_round {
	my ($s1, $s2, $center) = @_;
	my ($p1, $p2) = ($s1->{pt}[-1], $s2->{pt}[0]);
	my ($d1, $d2) = ($p1-$center, $p2-$center);
	my ($a1, $a2) = (($p1-$center)->angle, ($p2-$center)->angle);
	my $n_segs;
	if (($d1 ^ $d2) > 0) {
	#	return join_bevel($s1, $s2);
		$a2 += 2 * PI if $a2 < $a1;
		$n_segs = ($a2-$a1) / (PI/2);
	} else {
		$a1 += 2 * PI if $a1 < $a2;
		$n_segs = ($a1-$a2) / (PI/2);
	}
	if ($n_segs - int($n_segs) > .01) {
		$n_segs = int $n_segs+1;
	}
	return unless $n_segs;
	my $da = ($a2-$a1)/$n_segs;
	my $r = sqrt($d1->len2);
	my $t = $d1->normalize->rotate(90) * $r * _tan($da/4)*4/3;
	$da *= 180/PI;
	my @ret;
	for my $i (0 .. ($n_segs-1)) {
		my $from = $center + $d1->rotate($i * $da);
		my $to = $center + $d1->rotate(($i+1) * $da);
		push @ret, path_segment($from, $from + $t->rotate($i*$da),
				$to - $t->rotate(($i+1) * $da), $to)
	}
	$ret[0]{pt}[0] = $p1;
	$ret[-1]{pt}[-1] = $p2;
	@ret
}

sub join_segs {
	my ($s1, $s2, $opts) = @_;
	if (($s1->tangent(1, 1)^$s2->tangent(0)) > 0) {
		return path_segment($s1->{pt}[-1], $s2->{pt}[0]);
	}
	given($opts->{linejoin}) {
	when('bevel') { return join_bevel $s1, $s2 }
	when('miter') { return join_miter $s1, $s2, $opts->{anglelimit} }
	when('round') { return join_round $s1, $s2, $opts->{center} }
	}
}

package Graphics::PlanarVector::SubPath;
use Graphics::PlanarVector::SubPath;

sub parallel {
	my ($sp, $w) = (shift, shift);
	my %opts = (
		linejoin=>	'miter',
		miterlimit=>	10,
		@_);

	my $lim = 1/$opts{miterlimit};
	$opts{anglelimit} = 2 * $lim * $lim - 1;

	my @ret;
	for my $seg (@{$sp->{kids}}) {
		my @out = $seg->parallel($w);
		if (!@ret) {
			@ret = @out;
			next;
		}
		my ($last, $next) = ($ret[-1], $out[0]);
		unless ($last->{pt}[-1]->veq($next->{pt}[0])) {
			$opts{center} = $seg->{pt}[0];
			push @ret, $last->join_segs($next, \%opts);
		}
		push @ret, @out;
	}

	my $new = subpath();
	if ($sp->{closed}) {
		$opts{center} = $sp->{kids}[0]{pt}[0];
		push @ret, $ret[-1]->join_segs($ret[0], \%opts);
		$new->{closed} = 1;
	}
	$new->{kids} = \@ret;
	$new
}

sub _opts {
	{	linecap=>	'butt',
		linejoin=>	'miter',
		miterlimit=>	10,
		offset=>	0,
		@_
	};
}

sub sweep {
	my ($sp, $w) = (shift->dup, shift);
	my %opts = %{&_opts};

	$sp->close_sub;

	my $lim = 1/$opts{miterlimit};
	$opts{anglelimit} = 2 * $lim * $lim - 1;

	my (@ret, $next, $prev, $first, $last);
	for ($sp->kids, undef) {
		my $seg = $_;
		if (defined $seg) {
			my @out = $seg->parallel($w);
			$next = $out[-1];
			$first //= $out[0];

			my ($s, $sub) = ($seg->reverse, subpath);
			push @out, path_segment($next->{pt}[-1], $s->{pt}[0]), $s;

			@{$sub->{kids}} = @out;
			$sub->close_sub;
			push @ret, $sub;
		} else {
			$next = $first;
			$seg = $sp->{kids}[0];
		}

		if (defined $prev) {
			unless ($prev->{pt}[-1]->veq($next->{pt}[0])) {{
				last if (($prev->tangent(1,1)^$next->tangent(0)) >= 0);

				$opts{center} = $seg->{pt}[0];
				my $sub = subpath;
				my @out = $prev->join_segs($next, \%opts);
				push @out, path_segment($out[-1]{pt}[-1], $seg->{pt}[0]);
				@{$sub->{kids}} = @out;
				$sub->close_sub;
				push @ret, $sub;
			}}
		}
		$prev = $next;
	}

	@ret;
}

sub outline {
	my ($sp, $w) = (shift, shift);
	return unless $w;

	my %opts = %{&_opts};
	my $oft = $opts{offset};
	my ($left, $right) = (
		$sp->parallel($w/2 + $oft, %opts),
		$sp->reverse->parallel($w/2 - $oft, %opts)
	);
	return ($left, $right) if $sp->{closed};

	my (@cap1, @cap2);
	given($opts{linecap}) {
	when('butt') {
		@cap1 = path_segment($left->{kids}[-1]{pt}[-1],
				$right->{kids}[0]{pt}[0]);
		@cap2 =	path_segment($right->{kids}[-1]{pt}[-1],
				$left->{kids}[0]{pt}[0]);
	}
	when('square') {
		my $d = $left->{kids}[-1]->tangent(1,1) * $w/2;
		my ($p1, $p2) = ($left->{kids}[-1]{pt}[-1], $right->{kids}[0]{pt}[0]);
		@cap1 = (path_segment($p1, $p1 + $d),
			path_segment($p1 + $d, $p2 + $d),
			path_segment($p2 + $d, $p2));

		$d = $right->{kids}[-1]->tangent(1,1) * $w/2;
		($p1, $p2) = ($right->{kids}[-1]{pt}[-1], $left->{kids}[0]{pt}[0]);
		@cap2 = (path_segment($p1, $p1 + $d),
			path_segment($p1 + $d, $p2 + $d),
			path_segment($p2 + $d, $p2));
	}
	when('round') {
		my ($p1, $p2) = ($left->{kids}[-1]{pt}[-1], $right->{kids}[0]{pt}[0]);
		@cap1 = $left->{kids}[-1]->join_round($right->{kids}[0], ($p1+$p2)/2);

		($p1, $p2) = ($right->{kids}[-1]{pt}[-1], $left->{kids}[0]{pt}[0]);
		@cap2 = $right->{kids}[-1]->join_round($left->{kids}[0], ($p1+$p2)/2);
	}
	default { croak "bad line cap spec: $opts{linecap}" }
	}
	push @{$left->{kids}}, @cap1, @{$right->{kids}}, @cap2;
	$left->close_sub;

	return $left
}

package Graphics::PlanarVector::Path;
use Graphics::PlanarVector::Path;

sub parallel {
	my ($p, $w, @opts) = @_;
	path(map { $_->parallel($w, @opts) } $p->kids);
}

sub outline {
	my ($p, $w, %opts) = @_;
	path(map { $_->outline($w, @_) } $p->kids);
}

sub grow {
	my ($p, $w) = (shift, shift);
	my %opts = (linejoin=>'round', @_);
	return $p unless $w;

	$opts{evenodd} //= 0;
	$p = $p->unwind($opts{evenodd});
	if ($w > 0) {
		return path_or $p,
			map { path($_)->unwind }
			map {$_->sweep($w, %opts) } $p->kids;
	}

	$p = $p->reverse;
	$p->unwind;
	my @paths = map { path($_)->unwind } map { $_->sweep(-$w, %opts) } $p->kids;
	#$p - path_or @paths
	path_combine(@paths)
}

1;
